%\documentclass[13pt, a4paper]{report}

% import packges
%\usepackage{color,graphics,graphicx}
%\usepackage{mathpple,amsmath,mathrsfs}
%\usepackage{parskip}
% redefine some case

%\begin{document}
\chapter{Introduction}
\section{Moore's algorithm}
\subsection{Definitions and notation}
\subsubsection{Set, partitions and equivalence relations}

A set is an unordered collection of objects. Two sets called to be disjoint if they do not have the element common; for example, on the set A=\{0,1,2,3,4,5\}, the subset B= \{0, 2, 4\} and C=\{1, 3, 5\} are disjoint sets. A family of sets is pairwise disjoint if every two different sets in the family are disjoint.\\

A partition of a set E is a family nonempty $\mathcal{P} $, pairwise disjoint subsets of E such that $E=\bigcup_{\substack{P\in \mathcal{P}}}P$. A partition defines an equivalence relation $\sim_P$ on E. conversely, the set of all equivalence classes $[x]$,for $x \in E $, of an equivalence relation on E defines a partition of E.\\

Give two partition $\mathcal{P}$ and $\mathcal{Q}$ of a set E, we denote by $\mathcal{U} = \mathcal{P} \wedge \mathcal{Q}$ the coarsest partition which refines $\mathcal{P}$ and $\mathcal{Q}$. The classes of $\mathcal{U}$ are nonempty sets $P \cap Q$, for $ P\in\mathcal{P} and Q\in\mathcal{Q}$.
\subsubsection{Partitions and automata}
Let a deterministic automata $\mathcal{A}=(Q,\Sigma, \delta,q_0,F )$ over the alphabet $ \Sigma $. P is a subset of Q, denoted $P^c$ is another subset of Q where $P^c=Q \backslash P$.\\

Give a set $P \subset Q$ of states and a letter $ \alpha $, we denote $\alpha^{-1} P$  is the set of states q such that $ q.\alpha \in P$. Give sets $ P, R \subset Q$ and $ \alpha \in A$, we denote by $(P,\alpha)| R$ the partition of R composed of the nonempty sets among
\begin{center}
$R \cap \alpha^{-1}P = \{ q \in R| q.\alpha \in P \}$ and $R\backslash\alpha^{-1}P=\{ q \in R|q.\alpha \notin P \}$
\end{center}

An example, the partition $(F,\alpha)|Q$ is the partition of Q into the set of those states from which α is accepted, and the other ones.

\subsection{Moore's algorithm}
Moore is an algorithm about minimization automata given by Moore. The idea of algorithm computes the Nerode equivalence by a stepwise refinement of some initial equivalence. The automatons are assumed to be deterministic.
\subsubsection{Description}
Let $\mathcal{A} = (Q,\Sigma,\delta,q_0,F)$ be an automata over alphabet $\Sigma$. Define, for $ q \in Q $ and $ h \geq 0 $ the set
\begin{center}
${L_q^{(h)}(\mathcal{A})= \{ w \in \mathcal{A}^*||w|\leq h, q.w \in F \}}$ (*)
\end{center}
The Moore equivalence of order h is the equivalence $\sim_h$ defined for $h \geq 0$ by 
\begin{center}
$ p \sim_h q \Leftrightarrow {L_p^{(h)}}(\mathcal{A}) = {L_q^{(h)}}(\mathcal{A})$  with   ${L_q^{(h)}}(\mathcal{A})$  is  (*)
\end{center}
\subsubsection{Algorithm}
$MOORE(\mathcal{A})$\\
\-\hspace{0.5cm} $\mathcal{P} \leftarrow \{ F,F^c \} $\\
\-\hspace{0.5cm} repeat\\
\-\hspace{1cm} $\mathcal{Q} \leftarrow \mathcal{P} $\\
\-\hspace{1.5cm} for all $ a \in \Sigma$\\
\-\hspace{2cm} $ \mathcal{P}_a \leftarrow a^{-1}\mathcal{P} $\\
\-\hspace{1.5cm} $\mathcal{P} \leftarrow \mathcal{P} \wedge \bigwedge_{a \in A}\mathcal{P}_a $\\
\-\hspace{0.5cm} until $\mathcal{Q} = \mathcal{P} $\\
Where:
\begin{itemize}
\item $a^{-1}\mathcal{P}$ is the partition equivalence defined by 
\begin{center}
$p\sim q$ if and only if $L_p(\mathcal{A})=L_q(\mathcal{A})$
\end{center}
\item If $\mathcal{P}$ is the partition equivalence $\sim_h$, then $\mathcal{P'} = \mathcal{P} \wedge \bigwedge_{a \in A}\mathcal{P}_a $ is $\sim_{h+1}$
\end{itemize}
\subsubsection{Example}
Consider the automata below:
\begin{figure}[h!]
\includegraphics[scale=0.8]{images/automaton_1}
\centering
\caption{Automata 1}
\end{figure}\\\\\\
The result after find the equivalence on Automata 1:
\begin{figure}[h!]
\includegraphics{images/moore_demo}
\centering
\caption{Result run Moore on automata 1}
\end{figure}
%\end{document}